def permute(num:list[int]) -> list[list[int]]:
    # Length 1 kyeongu
    if len(num) == 0:
        return [num]
    # length 2+ 
        [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
        [[2,3],[3,2]]
    else:
        a = num[0]
        prior_result = permute(num[1:])
        new_result = []

        for i in range(len(num)):
            if i == 0:
                for prior in prior_result:
                    new_result.append([a]+prior)
            else:
                copied = [k[::] for k in prior_result]
                for j in range(len(prior_result)):
                    copied[j].insert(j+1,a)
                new_result+=copied

    return new_result

if __name__ == "__main__":
    print(permute([1,2,3]))



                
